



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 3, Exercise 9<BR>

<BR>

</H1>

<DL Compact>

<DT> (a)

<DD>

No changes are needed to the class definition.

<dt> (b)

<dd>

In an array of size <em class=var>n</em> we can represent a list of length at most

<em class=var>n-1</em> because position 0 is not used.

<dt> (c)

<dd>

The modified implementations are given below and in the file

<code class=code>llist1.h</code>.

</DL>

<HR class = coderule>

<PRE class = code>

template&lt;class T&gt;

LinearList&lt;T&gt;::LinearList(int MaxListSize)

{// Constructor for formula-based linear list.

   MaxSize = MaxListSize;

   element = new T[MaxSize+1];

   length = 0;

}



template&lt;class T&gt;

bool LinearList&lt;T&gt;::Find(int k, T&amp; x) const

{// Set x to the k'th element of the list.

 // Return false if no k'th; true otherwise.

   if (k &lt; 1 || k &gt; length) return false; // no k'th

   x = element[k];

   return true;

}



template&lt;class T&gt;

int LinearList&lt;T&gt;::Search(const T&amp; x) const

{// Locate x.  Return position of x if found.

 // Return 0 if x not in list.

   for (int i = 1; i &lt;= length; i++)

      if (element[i] == x) return i;

   return 0;

 }



template&lt;class T&gt;

LinearList&lt;T&gt;&amp; LinearList&lt;T&gt;::Delete(int k, T&amp; x)

{// Set x to the k'th element and delete it.

 // Throw OutOfBounds exception if no k'th element.

   if (Find(k, x)) {// move elements k+1, ..., down

      for (int i = k+1; i &lt;= length; i++)

         element[i-1] = element[i];

      length--;

      return *this;

      }

   else throw OutOfBounds();

}



template&lt;class T&gt;

LinearList&lt;T&gt;&amp; LinearList&lt;T&gt;::Insert(int k, const T&amp; x)

{// Insert x after the k'th element.

 // Throw OutOfBounds exception if no k'th element.

 // Throw NoMem exception if list is already full.

   if (k &lt; 0 || k &gt; length) throw OutOfBounds();

   if (length == MaxSize) throw NoMem();

   // move one up

   for (int i = length; i &gt; k; i--)

      element[i+1] = element[i];

   element[k+1] = x;

   length++;

   return *this;

}



template&lt;class T&gt;

void LinearList&lt;T&gt;::Output(ostream&amp; out) const

{// Put the list into the stream out.

   for (int i = 1; i &lt;= length; i++)

      out &lt;&lt; element[i] &lt;&lt; "  ";

}



// overload &lt;&lt;

template &lt;class T&gt;

ostream&amp; operator&lt;&lt;(ostream&amp; out, const LinearList&lt;T&gt;&amp; x)

   {x.Output(out); return out;}

</pre>

<HR class=coderule><BR>

<DL Compact>

<DT> (d)

<DD>

Test code and sample output appear in the files

<code class=code>llist1.*</code>.

<dt> (e)

<dd>

The complexity of each function is the same as when Equation 3.1

was used.

</dl>





</FONT>

</BODY>

</HTML>

